package com.cndym.utils;

import java.util.ArrayList;
import java.util.List;

public class CombinationUtils {
    public List<int[]> combination(int[] a, int m) {
        List<int[]> list = new ArrayList<int[]>();
        if (m >= a.length) {
            list.add(a);
            return list;
        }
        CombinationUtils c = new CombinationUtils();
        int n = a.length;
        boolean end = false;
        int[] tempNum = new int[n];
        for (int i = 0; i < n; i++) {
            if (i < m) {
                tempNum[i] = 1;

            } else {
                tempNum[i] = 0;
            }
        }
        list.add(c.createResult(a, tempNum, m));
        int k = 0;
        while (!end) {
            boolean findFirst = false;
            boolean swap = false;
            for (int i = 0; i < n; i++) {
                int l = 0;
                if (!findFirst && tempNum[i] == 1) {
                    k = i;
                    findFirst = true;
                }
                if (tempNum[i] == 1 && tempNum[i + 1] == 0) {
                    tempNum[i] = 0;
                    tempNum[i + 1] = 1;
                    swap = true;
                    for (l = 0; l < i - k; l++) {
                        tempNum[l] = tempNum[k + l];
                    }
                    for (l = i - k; l < i; l++) {
                        tempNum[l] = 0;
                    }
                    if (k == i && i + 1 == n - m) {
                        end = true;
                    }

                }
                if (swap) {
                    break;
                }
            }
            list.add(c.createResult(a, tempNum, m));
        }
        return list;
    }

    public int[] createResult(int[] a, int[] temp, int m) {
        int[] result = new int[m];
        int j = 0;
        for (int i = 0; i < a.length; i++) {
            if (temp[i] == 1) {
                result[j] = a[i];
                j++;
            }
        }
        return result;
    }
}
